import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * 去除重复字母
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/20 17:20
 */
public class RemoveDuplicateLetters {
    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("cbacdcbc"));
    }

    /**
     * @param s s由小写英文字母组成(1 <= s.length <= 104 )
     * @return
     */
    static public String removeDuplicateLetters(String s) {
//        (97~122)
//        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
        int[] x = new int[26];//记录字符最后一出现的位置
        boolean[] vis = new boolean[26];//记录字符是否在栈中
        StringBuilder str = new StringBuilder();
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) x[charArray[i] - 'a'] = i;

        for (int i = 0; i < charArray.length; i++) {
            if (vis[charArray[i] - 'a']) continue; //当前字符已在栈中
            if (str.length() == 0) { //将加入顶栈
                str.append(charArray[i]);
                vis[charArray[i] - 'a'] = true;
                continue;
            }
            while (str.length() > 0 && str.charAt(str.length() - 1) > charArray[i]) {//当前字符小于顶栈字符且未加入栈中
                if (x[str.charAt(str.length() - 1)-'a'] < i) { //顶栈字符最后一次出现
                    break;
                } else {//清除顶栈
                    vis[str.charAt(str.length() - 1) - 'a'] = false;
                    str.deleteCharAt(str.length() - 1);
                }
            }
            str.append(charArray[i]);
            vis[charArray[i] - 'a'] = true;
        }
        return str.toString();
    }

}
